package org.pupil.queue;

import java.util.Stack;

/**
 * @Description: 使用栈实现队列  leetcode：https://leetcode.cn/problems/implement-queue-using-stacks
 * 每个操作时间复杂度均摊下来是：O(1)，每个元素进出最多各两次
 * in栈：压入数据时元素进行一次进操作，倒数据时元素再进行一次出操作
 * out栈：倒数据时元素进行一次进操作，获取数据时元素再进行一次出操作
 * 空间复杂度：O(1)，申请了两个栈实现
 * @Author: pupil
 * @Date: 2024/08/04 下午 2:12
 */
public class MyQueue {

    private Stack<Integer> in;
    private Stack<Integer> out;

    public MyQueue() {
        in = new Stack<>();
        out = new Stack<>();
    }

    // 倒数据
    // 从in栈，把数据倒入out栈
    // 1）out空了，才能倒数据
    // 2）如果倒数据，in必须倒完
    private void inToOut() {
        if (out.empty()) {
            while (!in.empty()) {
                out.push(in.pop());
            }
        }
    }


    // 入队
    public void push(int num) {
        in.push(num);
        inToOut();
    }

    // 出队
    public int pop() {
        inToOut();
        return out.pop();
    }

    // 获取队列元素（不弹出）
    public int peek() {
        inToOut();
        return out.peek();
    }

    // 判断队列是否为空
    public boolean empty() {
        return in.empty() && out.empty();
    }
}
